Data compression is an extremely useful tool for storing and transmitting large amounts of data. For example, when compression is used to decrease the number of bits relative to the original image size, the amount of data transmitted is reduced and the time required to transmit the image can be reduced. For instance, it is known for a graphics processor to compress texture values representing an image. The compressed texture values may then be transmitted from one device to another, such as a computer, handheld device, portable phone, personal data assistant (PDA), wireless communication network or any suitable network element.
Block truncation coding (BTC) is an image processing technique for encoding and decoding digital image data, based on N×M (e.g., four-by-four) nonoverlapping “pixel” blocks. Color cell compression (CCC) is one example of extending the BTC method to color. The pixels of the block are partitioned into two groups, a representative color is chosen for each of these two groups, and a bitmap is generated with individual bits to indicate which group each pixel in the block is associated with. The compressed data for such a block typically consists of only two color values, or two color indices into a color palette, and the bitmap indicating which of the two groups each pixel belongs to. However, encoding only two colors for any given block may result in poor image quality, especially for blocks with diverse colors.
Digital color images may be compressed by encoding the chrominance (color) and luminance (brightness) values for each pixel contained therein. The color values may be described using a three component color space, such as an RGB component color space, where R represents the color red, G represents the color green and B represents the color blue. Eight-bit color values for each component may range from 0 to 255, with 255 representing the maximum amount of color or the highest value in the range. The combination of three eight-bit color components results in a 24-bit total color value per pixel. However, any number of bits per color, such as 16 bits, 32 bits, 64 bits or any other suitable number of bits, may represent the color of a pixel. Colors may alternatively be represented by a YIL color space, as is known in the art. Yet another color space, the CIE L*a*b* color space, represents a color based on components of luminance, labeled L*, a relative amount of red versus green, labeled a*, and a relative amount of yellow versus blue, labeled b*. Colors in these color spaces are then blended together in appropriate ways in order to produce a full spectrum of colors. In the L*a*b* luminance-chrominance color space, an L*=0 (luminance) value means that no light is present (i.e., the pixel location is completely black), while a*=0 means no red or green is present and b*=0 means that the pixel location is neither blue nor yellow. The occurrence of both a*=0 and b*=0 together means that the pixel location is gray (somewhere between black and white). In contrast, the hexidecimal value 255 represents the maximum amount of a color or the highest value in the range (maximum light/white, red and yellow, respectively, for L*a*b*). Similarly, in a gray-scale pixel map, pixel values may range from 0 for black to 255 for the whitest tone possible.
Since BTC/CCC methods quantize each block to just two representative colors or luminance values, image degradation may be significant. Some variations of BTC/CCC encode two representative colors, but imply one or two additional colors based on the two encoded colors. If the colors in the block are relatively dispersed, such as when the colors include near black and bright colors, then the two representative colors may not properly represent the colors in the original image. For example, if the two representative color values represent the intermediate colors, then the two representative color values may not accurately represent extreme colors, such as black and white. If the two color levels that are selected to represent each block are not properly representative of the block, then the colors in the final decoded output image may not accurately represent those in the original image.
BTC/CCC methods are also known to encode pixel information for each of the colors red, green and blue as separate BTC/CCC blocks. As a result, these methods produce six code words (i.e. R1, R2, G1, G2, B1, B2)) and three separate bitmaps to indicate how each channel should be reconstructed. This method of adapting BTC to color comes at the cost of bitmap data that is three times larger than the other algorithms use.
A variation of CCC stores two encoded colors as eight-bit indices into a 256-entry code book lookup table. However, such pixel blocks cannot be decoded without fetching additional information, which increases computational complexity and can consume additional memory bandwidth. Further, the transmission of a code book decreases system performance due to the increased data transmission and the additional overhead due to the required memory accesses to translate code words via the code book. As a result, these methods may be memory-intensive in terms of speed and bandwidth, and further may require large amounts of memory. Additionally, two colors may not properly represent diverse colors in the original image.
BTC methods are also known to perform three-level block truncation coding of color images. Two representative colors are encoded along with a bitmap containing two bits per pixel to indicate which of the three color levels each pixel belongs. One of the three color levels is derived from the two encoded colors—usually the color half way between them. A known extension of this method is to use the two bits per pixel in the bitmap to represent four levels instead of three and to derive the two additional colors one-third and two-thirds of the way between the two encoded colors. However, if the colors in the block are relatively dispersed, such as when the colors include near black, near white, and some other more saturated color, then the two encoded colors, along with any implied colors, may not properly represent the colors in the original image. Since blending two of the three colors will not produce the third color in this scenario, the final decoded image may not accurately represent those in the original image
Four level CCC methods that encode two colors to provide for three or four colors are also known to further provide information on which pixels, if any, are transparent. The transparency block type indicates whether one of the color levels indicates an actual color level or indicates that the corresponding pixel is transparent. Further, according to this known method, the transparency block type is indicated based on whether one code word is greater than another, rather than on an encoded data bit.